#include <stdio.h>
#include <string.h>
#include <assert.h>
#include <stdlib.h>

int* build_next(const char* str)
{
    assert(str);
    int len = strlen(str);
    int* next = (int*)malloc(sizeof(int) * len);
    int common_len = 0;//记录共同前后缀长度
    int i = 1;
    next[0] = 0;//第一个位置对应的字符串只有一个元素，无前后缀之说
    while(i < len)
    {
        if(str[common_len] == str[i])//前后缀匹配成功，长度加一，并保存在当前位置
        {
            common_len++;
            next[i] = common_len;
            i++;
        }
        else//前后缀匹配失败
        {
            if(common_len == 0)
            {
                next[i] = 0;
                i++;
            }
            else
            common_len = next[common_len - 1];//利用已创建的部分next数组，使得common_len少进行回溯
        }
    }
    return next;
}

char* kmp_search(const char* str1, const char* str2)
{
    assert(str1 && str2);
    int* next = build_next(str2);

    int i = 0;
    int j = 0;
    while(i < strlen(str1))
    {
        if(str1[i] == str2[j])//匹配成功，i，j各加一以匹配下一对
        {
            i++;
            j++;
        }
        else if(j > 0)//匹配失败，根据已匹配部分的最长共同前后缀长度回溯j
        j = next[j - 1];
        else//第一个字符就不匹配
        i++;
        
        if(j == strlen(str2))
        return (char*)str1 + i - j;
    }

    return NULL;
}

int main()
{
    char* arr1 = "abababcabc";
    char* arr2 = "ababc";
    printf("%s\n", kmp_search(arr1, arr2));
    return 0;
}